package com.company.test24;

/**
 * Created by Administrator on 2016.10.19.
 */
public class Test2402 {
    public static void main(String[] args) {
        Integer[] a={1,4,6,2,3,7,4,13,8,9};

        mergeSort(a);

        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }

    public static <E extends Comparable<E>> void mergeSort(E[] list){
        if(list.length<1){
            return;
        }

        mergeSort(list,0,list.length-1);
    }

    private static <E extends Comparable<E>> void mergeSort(E[] list,int low,int hight){
        if(hight<=low){
            return;
        }

        int mid=(hight+low)/2;

        mergeSort(list,low,mid);
        mergeSort(list,mid+1,hight);
        mergeSort(list,low,mid,hight);
    }

    private static <E extends Comparable<E>> void mergeSort(
            E[] list,int low,int middle,int hight){
        int current1=low;
        int current2=middle+1;
        int current3=low;

        E[] target=list.clone();

        while (current1<=middle&&current2<=hight){
            if(list[current1].compareTo(list[current2])<0){
                target[current3++]=list[current1++];
            }else{
                target[current3++]=list[current2++];
            }
        }

        while (current1<=middle){
            target[current3++]=list[current1++];
        }

        while (current2<=hight) {
            target[current3++] = list[current2++];
        }

        System.arraycopy(target,low,list,low,hight-low+1);
    }
}
